#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // 包含INT_MAX的定义
using namespace std;

class Solution {
public:
    // 验证函数：判断能否以至少x的间距放置m个球
    bool check(int x, vector<int>& a, int m) {
        int cnt = 0; // 记录已形成的有效间隔数（m个球需要m-1个间隔）
        int target = a[0] + x; // 第一个球放在a[0]，下一个球的最小位置
        for (int i = 0; i < a.size() - 1; i++) {
            // 找到第一个>=target的位置，放置下一个球
            if (a[i] < target && a[i + 1] >= target) {
                cnt++;
                target = a[i + 1] + x; // 更新下一个球的最小位置
            }
        }
        return cnt >= m - 1; // 间隔数足够则返回true
    }
    
    int maxDistance(vector<int>& position, int m) {
        vector<int>& a = position; // 统一变量名，避免混淆
        sort(a.begin(), a.end()); // 排序位置数组（必须先排序）
        int len = a.size();
        int maxd = a[len - 1] - a[0]; // 最大可能间距（首尾差）
        int mind = INT_MAX; // 最小可能间距（相邻元素的最小差）
        
        // 计算相邻元素的最小间距
        for (int i = 0; i < len - 1; i++) {
            mind = min(mind, a[i + 1] - a[i]);
        }
        
        // 特判：m=2时，最大间距就是首尾差
        if (m == 2) {
            return maxd;
        } else {
            // 二分查找：左边界为最小间距，右边界为理论最大可能的最小间距
            int l = mind;
            int r = maxd / (m - 1);
            while (l <= r) {
                int mid = (l + r) / 2; // 当前猜测的最小间距
                if (check(mid, a, m)) {
                    // 能放下，尝试更大的间距
                    l = mid + 1;
                } else {
                    // 放不下，尝试更小的间距
                    r = mid - 1;
                }
            }
            return l - 1; // 退出时l-1是最大有效间距
        }
    }
};